This invention relates to simple burst error correcting cyclic codes and the generation method thereof for use in a burst error trapping decoder, which can dramatically enhance burst error correcting capability of existing burst correcting cyclic codes with a simple decoding method. Particularly, this invention relates to simple burst error correcting cyclic codes and the generation method thereof for use in a burst error trapping decoder, for correction of bursts up to nearly twice the guaranteed correction bound.
Although many coding techniques have been developed for channels on which transmission errors occur independently in digit positions, communication channels such as telephone lines can be affected by lightning strikes or man-made electrical disturbances that cause transmission errors to cluster into bursts. Since random error correcting codes are inefficient for correcting such burst errors, it is desirable to design codes specifically for correcting burst errors. Codes of this kind are called burst error correcting codes.
Cyclic codes are effective not only for burst error detection but also for burst error correction. Various effective cyclic codes for correcting burst errors have been proposed over the past twenty years.
For cyclic codes, the correction of all bursts within the guaranteed Reiger burst error correcting capability of the code is accomplished with a simple burst error trapping method using a feedback shift register (reference Error Control Coding: Fundamentals and Applications by S. Lin and D. J. Costello, Jr., Prentice-Hall, 1983). It has also been recognized that with a high degree of confidence a very large proportion of bursts of a length well beyond the guaranteed burst error correcting capability can be corrected, but with greater difficulty. The simplest general method finds the shortest burst having a given syndrome (reference pp 291-297 of Information Theory and Reliable Communication by R. G. Gallager, Wiley, 1968). The Gallager scheme requires two passes through shift registers: one to find the shortest burst and the other to do the correction thereon. This method is significantly more complex than burst error trapping, however, which performs the decoding in one pass. Another method corrects bursts beyond the guaranteed correctable bound using Reed-Solomon codes (reference "A Burst-Error Algorithm for Reed-Solomon Codes" by J. Chen and P. Owsley, in IEEE Transactions on Information Theory, pp 1807-1812, November 1992). Decoding Reed-Solomon codes is also considerably more complex than burst error trapping. The number of check symbols was an absolute bound on burst error correction capability with any satisfactory degree of confidence.
Referring to FIG. 1 showing a burst error trapping decoder for burst error correcting codes, a decoding operation of single burst error correcting cyclic codes will be described in more detail below.
As shown in FIG. 1, an l-burst-error-correcting cyclic code can be most easily decoded by the error-trapping technique, with a slight variation. Suppose that a code word v(X) from an l-burst-error-correcting (n, k) cyclic code is transmitted. Let r(X) and e(X) be the received and error vectors, respectively, and let EQU s(X)=s.sub.0 +s.sub.1 X+ . . . +s.sub.n-k-1 X.sup.n-k-1
be the syndrome of r(X). Then, if the errors in e(X) are confined to the l higher-order parity-check digit positions X.sup.n-k-l , . . . , X.sup.n-k -2 and X.sup.n-k-1 of r(X), the l higher-order syndrome digits S.sub.n-k-l, . . . , S.sub.n-k-2 and s.sub.n-k-1 match the errors of e(X) and the n-k-l lower-order syndrome digits s.sub.0, s.sub.1, . . . and s.sub.n-k-l-1 are zeros. Suppose that the errors in e(X) are not confined to the positions X.sup.n-k-l, . . . , X.sup.n-k-2 and X.sup.n-k-1 of r(X) but are confined to l consecutive positions of r(X) (including the end-around case). Then, after a certain number of cyclic shifts of r(X), say, i cyclic shifts, the errors will be shifted to the positions X.sup.n-k-l, . . . , X.sup.n-k-2 and X.sup.n-k-1 of r.sup.(l) (X), the ith shift of r(X). Let s.sup.(l) (X) be the syndrome of r.sup.(l) (X) . Then, the first l higher-order digits of s.sup.(l) (X) match the errors at the positions X.sup.n-k-l, . . . , X.sup.n-k-2 and X.sup.n-k-1 of r.sup.(l) (X), and the n-k-l lower-order digits of s.sup.(l) (X) are zeros. Using these facts, the errors in the syndrome register can be trapped by cyclic-shifting r(X) .
In the error trapping decoder for an l-burst-error-correcting cyclic code shown in FIG. 1, the received vector is shifted into the syndrome register from the left end. The decoding procedure is described in the following steps:
Step 1. The received vector r(X) is shifted into the syndrome register and buffer register simultaneously. If it is not desired to decode the received parity check digits, the buffer register needs only k stages. As soon as r(X) has been shifted into the syndrome register, the syndrome s(X) is formed.
Step 2. The syndrome register starts to shift with gate 2 on. As soon as its n-k-l leftmost stages contain only zeros, its l rightmost stages contain the burst error pattern and the error correction begins. There are three cases to be considered.
Step 3. If the n-k-l leftmost stages of the syndrome register contain all zeros after the ith shift (for O.ltoreq.i.ltoreq.n-k-l), the errors of the burst e(X) are confined to the parity check positions of r(X). In this event, the k received information digits in the buffer register are error-free. Gate 4 is then activated and the k error-free information digits in the buffer are shifted out to the data sink. If the n-k-l leftmost stages of the syndrome register never contain all zeros during the first n-k-l shifts of the syndrome register, the error burst is not confined to the n-k parity-check positions of r(X).
Step 4. If the n-k-l leftmost stages of the syndrome register contain all zeros after the (n-k-l+i)th shift of the syndrome register for 1.ltoreq.i.ltoreq.l, the error burst is confined to positions X.sup.n-l, . . . , X.sup.n-1, X.sup.0, . . . , and X.sup.l-i-1 of r(X). This is an end-around burst. In this event, the l-i digits contained in the l-i rightmost stages of the syndrome register match the errors at the parity check positions X.sup.0, X.sup.1, . . . , and X.sup.l-i-1 of r(X), and the i digits contained in the next i stages of the syndrome register match the errors at the positions X.sup.n-l, . . . , X.sup.n-2 and X.sup.n-1 of r(X). At this instant, a clock starts to count from (n-k-l+i+1). The syndrome register is then shifted (in step with the clock) with gate 2 turned off. As soon as the clock has counted up to n-k, the i rightmost digits in the syndrome register match the errors at the positions X.sup.n-l, . . . , X.sup.n-2 and X.sup.n-1 of r(X). Gates 3 and 4 are then activated. The received information digits are read out of the buffer register and corrected by the error digits shifted out from the syndrome register.
Step 5. If the n-k-l leftmost stages of the syndrome register never contains all zeros by the time that the syndrome register has been shifted n-k times, the received information digits are read out of the buffer register one at a time with gate 4 activated. At the same time, the syndrome register is shifted with gate 2 activated. As soon as the n-k-l leftmost stages of the syndrome register contain all zeros, the digits in the l rightmost stages of the syndrome register match the errors in the next l received information digits to come out of the buffer register. Gate 3 is then activated and the erroneous information digits are corrected by the digits coming out from the syndrome register with gate 2 disabled.
If the n-k-l stages of the syndrome register never contain all zeros by the time the k information digits have been read out of the buffer, an uncorrectable burst of errors has been detected. With the prior-art burst error trapping decoder described above, the decoding process takes 2n clock cycles; the first n clock cycles are required for syndrome computation and the next n clock cycles are needed for error trapping and error correction. The n clock cycles for syndrome computation are concurrent with the reception of the received vector from the channel; that is, no time delay occurs in this operation. The second n clock cycles for error trapping and correction represent a decoding delay.
In the decoder using the above-described decoding procedure, the received vector is shifted into the syndrome register from the left end. If the received vector is shifted into the syndrome register from the right end, the decoding operation would be slightly different.
This decoder corrects only burst errors of length l or less. The number of these burst error patterns is n2.sup.l-1, which, for a large n value, is only a small fraction of 2.sup.n-k correctable error patterns (the coset leaders).
It is possible to modify the decoder in such a way that it corrects all the correctable burst errors of length n-k or less. That is, besides correcting all the bursts of length l or less, the decoder also corrects those bursts of length l+1 to n-k which are used as coset leaders. This modified decoder operates as follows. The entire received vector is first shifted into the syndrome register. Before performing the error correction, the syndrome register is cyclically shifted n times (with feedback connections operative). During this cycling, the length b of the shortest burst that appears in the b rightmost stages of the syndrome register is recorded by a counter. This burst is assumed to be the error burst added by the channel. Having completed these pre-correction shifts, the decoder begins its correction process. The syndrome register starts to shift again. As soon as the shortest burst reappears in the b rightmost stages of the syndrome register, the decoder starts to make corrections as described earlier. This decoding is a well-known optimum decoding method for burst-error-correcting codes, which was proposed by Gallager.
However, as shown in FIG. 2, when the conventional cyclic codes are used, the test bit area in the (n-k)-stage syndrome register occupies more than half of the total number of the syndrome bits by the Reiger bound. Accordingly, the burst error correctable area cannot be extended.